#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 
子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
解题思路：
改题目结合了子集和组合总和2
*/

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums,int index,vector<int> used)
{   
    result.push_back(path);
    //递归终止条件
    if(index>=nums.size())
        return;
    for(int i=index;i<nums.size();i++)
    {
        //进行树层去重
        if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)
            continue;
        path.push_back(nums[i]);
        used[i] = 1;
        backtracking(nums,i+1,used);
        path.pop_back();
        used[i] = 0;
    }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    vector<int> used(nums.size(),0);
    sort(nums.begin(),nums.end());
    backtracking(nums,0,used);
    return result;
}
int main()
{
    cout<<"enter number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    result = subsetsWithDup(nums);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {   
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}